package mmo.astar
{
	import flash.geom.Point;
	
	/**
	 * 跨地图寻路 
	 * @author qiangchen
	 * @example 地图传送配置规则: 例如一个地图的id为1002，那么1002可以传送的地图为上、下、左、右以及斜上、斜下
	 * 8个格子（也就是1002所在格子的周围8个格子）；如果1002不能传送任何地图，那么它的周围8个格子都应填写-1（代表阻挡）。 
	 * <listing version="3.0">
	 * 地图传送matrix写法例子：
	 * [
	 *  -1,		1017,		-1,			-1,			-1,			-1,			-1,			-1,
	 *  -1,		-1,			1010,		1010,		1010,		1007,		-1,			-1,
	 *  -1,		1016,		-1,			1015,		-1,			-1,			1006,		-1,
	 *  -1,		-1,			1014,		-1,			-1,			1008,		-1,			-1,
	 *  -1,		1013,		-1,			-1,			-1,			-1,			1005,		-1,
	 *  1018,	-1,			1011,		1011,		-1,			-1,			-1,			1004,
	 *  -1,		1012,		-1,			1011,		-1,			-1,			1002,		-1,
	 *  -1,		-1,			-1,			1011,		-1,			-1,			-1,			1003,
	 *  -1,		-1,			-1,			1011,		1011,		-1,			1002,		-1,
	 *  -1,		-1,			-1,			-1,			-1,			1009,		-1,			1001
	 * ]
	 * 
	 * data[y][x] = array[index];
	 * 
	 * val = 
	 *	  	var index:int = array.indexOf( mapId );
	 *	  	var _row:int = ( index / col  >> 0 );
	 *	 	var _col:int = ( index % col >> 0 );
	 *	  	return _row<<16|_col;
	 *              ↓
	 * posx = ( val & 0xFF );
	 * posy = ( val >> 16 & 0xFF );
	 * 
	 * path = mapAstar.find( startx, starty, endx, endy );
	 * path = path.filter( function(item:*, index:int, array:Array):Boolean{ return item == 0 ? false : true } );
	 * </listing>
	 */	
	public class MapAStar
	{
		private const COST_DIAGONAL:int = 14;
		private const COST_STRAIGHT:int = 10;
		private const NOTE_ID:int = 0;
		private const NOTE_OPEN:int = 1;
		private const NOTE_CLOSED:int = 2;
		
		/** 格子数据 */
		private var m_mapTileModel:Array;
		/** 最大测试次数 */
		private var m_maxTry:int;
		/** 开放列表计数器 */
		private var m_openCount:int; 
		/** 开放列表编号 */
		private var m_openId:int; 
		/** 测试点列表 */
		private var m_openList:Array;
		/** x轴列表 */
		private var m_xList:Array;
		/** y轴列表 */
		private var m_yList:Array;
		/** 路径评分列表 */
		private var m_pathScoreList:Array;
		/** 移动耗费列表 */
		private var m_movementCostList:Array;
		/** 距离列表 */
		private var m_fatherList:Array;
		/** 地图id列表 */
		private var m_noteMap:Array;
		/** 地图数据最大行 */
		private var maxRow:int;
		/** 地图数据最大列 */
		private var maxColumn:int;
		
		/**
		 * 构造函数 
		 * @param p_mapTileModel 地图数据二维数据组
		 * @param p_maxTry	最大尝试次数
		 * 
		 */		
		public function MapAStar(p_mapTileModel:Array, p_maxTry:int = 1000)
		{
			this.m_mapTileModel = p_mapTileModel;
			this.maxRow = this.m_mapTileModel.length;
			this.maxColumn = this.m_mapTileModel[0].length;
			this.m_maxTry = p_maxTry;
		}
		
		/**
		 * 通过点获取地图id 
		 * @param tx
		 * @param ty
		 * @return 
		 * 
		 */		
		private function getMapId(tx:int,ty:int):int
		{
			return this.m_mapTileModel[ty][tx];
		}
		
		/**
		 * 检测是否此点为不可行走点 
		 * @param tx
		 * @param ty
		 * @return 
		 * 
		 */		
		private function checkBlock(tx:int,ty:int):Boolean
		{
			if(ty < 0 || ty >= this.maxRow || tx < 0 || tx >= this.maxColumn){
				return true;
			}
			return this.m_mapTileModel[ty][tx]==-1;
		}
		
		
		/**
		 * 寻路 
		 * @param p_startX
		 * @param p_startY
		 * @param p_endX
		 * @param p_endY
		 * @return 
		 * 
		 */		
		public function find(p_startX:int, p_startY:int, p_endX:int, p_endY:int) : Array
		{
			var try_count:uint = 0;
			var cur_id:int = 0;
			var p_x:int = 0;
			var p_y:int = 0;
			var cost:int = 0;
			var score:int = 0;
			var node_id:int = 0;
			var _arounds:Array = null;
			
			this.initLists();
			this.m_openCount = 0;
			this.m_openId = -1;
			this.openNote(p_startX, p_startY, 0, 0, 0);
			
			while(this.m_openCount > 0)
			{
				if (++try_count >= this.m_maxTry)
				{
					this.destroyLists();
					return null;
				}
				
				cur_id = this.m_openList[0];
				this.closeNote(cur_id);
				p_x = this.m_xList[cur_id];
				p_y = this.m_yList[cur_id];
				
				if (p_x == p_endX && p_y == p_endY)
				{
					return this.getPath(p_startX, p_startY, cur_id);
				}
				_arounds = getArounds(p_x,p_y);
				for each(var _temps:Array in _arounds)
				{
					cost = this.m_movementCostList[cur_id] + (_temps[0] != p_x && _temps[1] == p_y ? (COST_STRAIGHT) : (COST_DIAGONAL));
					//相同地图点cost为0
					if(getMapId(p_x,p_y)==getMapId(_temps[0],_temps[1]))
					{
						cost=0;
					}
					
					score = cost + (Math.abs(p_endX - _temps[0]) + Math.abs(p_endY - _temps[1])) * COST_STRAIGHT;
					if (this.isOpen(_temps[0], _temps[1]))
					{
						node_id = this.m_noteMap[_temps[1]][_temps[0]][NOTE_ID];
						if (cost < this.m_movementCostList[node_id])
						{
							this.m_movementCostList[node_id] = cost;
							this.m_pathScoreList[node_id] = score;
							this.m_fatherList[node_id] = cur_id;
							this.aheadNote(this.getIndex(node_id));
						}
						continue;
					}
					this.openNote(_temps[0], _temps[1], score, cost, cur_id);
				}
			}
			this.destroyLists();
			return null;
		}
		
		private function getArounds(p_x:int, p_y:int) : Array
		{
			var _cur_px:int = 0;
			var _cur_py:int = 0;
			var _arounds:Array = [];
			_cur_px = p_x + 1;
			_cur_py = p_y;
			var isBlock:Boolean = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x;
			_cur_py = p_y + 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x;
			_cur_py = p_y - 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x + 1;
			_cur_py = p_y + 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y + 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x - 1;
			_cur_py = p_y - 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			_cur_px = p_x + 1;
			_cur_py = p_y - 1;
			isBlock = checkBlock(_cur_px, _cur_py);
			
			if (!isBlock && !this.isClosed(_cur_px, _cur_py))
			{
				_arounds.push([_cur_px, _cur_py]);
			}
			return _arounds;
		}
		
		/**
		 * 获取最终路径 
		 * @param p_startX
		 * @param p_startY
		 * @param p_id
		 * @return 
		 * 
		 */		
		private function getPath(p_startX:int, p_startY:int, p_id:int) : Array
		{
			var _path:Array = [];
			var p_x:int = this.m_xList[p_id];
			var p_y:int = this.m_yList[p_id];
			
			while(p_x != p_startX || p_y != p_startY)
			{
				_path.unshift( getMapId( p_x, p_y) );
				p_id = this.m_fatherList[p_id];
				p_x = this.m_xList[p_id];
				p_y = this.m_yList[p_id];
			}
			this.destroyLists();
			return _path;
		}
		
		private function openNote(p_x:int, p_y:int, p_score:int, p_cost:int, p_fatherId:int) : void
		{
			this.m_openCount++;
			this.m_openId++;
			
			if (this.m_noteMap[p_y] == null)
			{
				this.m_noteMap[p_y] = [];
			}
			this.m_noteMap[p_y][p_x] = [];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = true;
			this.m_noteMap[p_y][p_x][NOTE_ID] = this.m_openId;
			this.m_xList.push(p_x);
			this.m_yList.push(p_y);
			this.m_pathScoreList.push(p_score);
			this.m_movementCostList.push(p_cost);
			this.m_fatherList.push(p_fatherId);
			this.m_openList.push(this.m_openId);
			this.aheadNote(this.m_openCount);
		}
		
		private function closeNote(p_id:int) : void
		{
			this.m_openCount--;
			
			var p_x:int = this.m_xList[p_id];
			var p_y:int = this.m_yList[p_id];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = false;
			this.m_noteMap[p_y][p_x][NOTE_CLOSED] = true;
			if (this.m_openCount <= 0)
			{
				this.m_openCount = 0;
				this.m_openList = [];
				return;
			}
			//			trace(this.m_openList);
			this.m_openList[0] = this.m_openList.pop();
			//			trace(this.m_openList);
			this.backNote();
		}
		
		private function backNote() : void
		{
			var _open_id:int = 0;
			var _cur_id:int = 1;
			while (true)
			{
				_open_id = _cur_id;
				if (2 * _open_id <= this.m_openCount)
				{
					if (this.getScore(_cur_id) > this.getScore((2 * _open_id)))
					{
						_cur_id = 2 * _open_id;
					}
					
					if ((2 * _open_id + 1) <= this.m_openCount)
					{
						if (this.getScore(_cur_id) > this.getScore((2 * _open_id + 1)))
						{
							_cur_id = 2 * _open_id + 1;
						}
					}
				}
				if (_open_id == _cur_id)
				{
					break;
				}
				var _temp_id:int = this.m_openList[_open_id - 1];
				this.m_openList[_open_id - 1] = this.m_openList[_cur_id - 1];
				this.m_openList[_cur_id - 1] = _temp_id;
			}
		}
		
		private function aheadNote(p_index:int) : void
		{
			var ahead:int = 0;
			while (p_index > 1)
			{
				ahead = Math.floor(p_index / 2);
				if (this.getScore(p_index) < this.getScore(ahead))
				{
					var openId:int = this.m_openList[p_index-1];
					this.m_openList[p_index - 1] = this.m_openList[ahead-1];
					this.m_openList[ahead-1] = openId;
					p_index = ahead;
					continue;
				}
				break;
			}
		}
		
		/**
		 * 通过点索引值获取此点的评分值 
		 * @param p_index
		 * @return 
		 * 
		 */		
		private function getScore(p_index:int) : int
		{
			return this.m_pathScoreList[this.m_openList[p_index-1]];
		}
		
		/**
		 * 初始化数据列表 
		 * 
		 */		
		private function initLists() : void
		{
			this.m_openList = [];
			this.m_xList = [];
			this.m_yList = [];
			this.m_pathScoreList = [];
			this.m_movementCostList = [];
			this.m_fatherList = [];
			this.m_noteMap = [];
		}
		
		/**
		 * 销毁测试数据列表 
		 * 
		 */		
		private function destroyLists() : void
		{
			this.m_openList.length = 0;
			this.m_openList = null;
			
			this.m_xList.length = 0;
			this.m_xList = null;
			
			this.m_yList.length = 0;
			this.m_yList = null;
			
			this.m_pathScoreList.length = 0;
			this.m_pathScoreList = null;
			
			this.m_movementCostList.length = 0;
			this.m_movementCostList = null;
			
			this.m_fatherList.length = 0;
			this.m_fatherList = null;
			
			this.m_noteMap.length = 0;
			this.m_noteMap = null;
		}
		
		/**
		 * 当目标点为不可行走点时，寻找最近的可行走点  
		 * @param p_startX
		 * @param p_startY
		 * @param p_endX
		 * @param p_endY
		 * @return 
		 * 
		 */		
		private function resetTarget(p_startX:int, p_startY:int, p_endX:int, p_endY:int) : Point
		{
			var try_count:uint = 0;
			while(checkBlock(p_endX, p_endY))
			{
				
				if (++try_count >= this.m_maxTry)
				{
					return null;
				}
				if(p_endX > p_startX){
					p_endX--;
				}else if(p_endX < p_startX){
					p_endX++;
				}
				
				if(p_endY > p_startY){
					p_endY--;
				}else if(p_endY < p_startY){
					p_endY++;
				}
			}
			return new Point(p_endX, p_endY);
		}
		
		private function getIndex(p_id:int) : int
		{
			var _open_id:int = 0;
			var _index:int = 1;
			for each (_open_id in this.m_openList)
			{
				
				if (_open_id == p_id)
				{
					return _index;
				}
				_index++;
			}
			return -1;
		}
		
		/**
		 * 此点是否正在计算列表中
		 * @param p_x
		 * @param p_y
		 * @return 
		 * 
		 */		
		private function isOpen(p_x:int, p_y:int) : Boolean
		{
			if (this.m_noteMap[p_y] == null)
			{
				return false;
			}
			if (this.m_noteMap[p_y][p_x] == null)
			{
				return false;
			}
			return this.m_noteMap[p_y][p_x][NOTE_OPEN];
		}
		
		/**
		 * 此点是否已经被淘汰
		 * @param p_x
		 * @param p_y
		 * @return 
		 * 
		 */		
		private function isClosed(p_x:int, p_y:int) : Boolean
		{
			if (this.m_noteMap[p_y] == null)
			{
				return false;
			}
			if (this.m_noteMap[p_y][p_x] == null)
			{
				return false;
			}
			return this.m_noteMap[p_y][p_x][NOTE_CLOSED];
		}
	}
}